package com.cdream.basic.algorithm.leetcode.array;

import java.util.PriorityQueue;

/**
 * @author cdream
 * @date 2022/3/19
 */
public class Question6020 {
    public int halveArray(int[] nums) {
        PriorityQueue<Double> pq =new PriorityQueue<Double>((a,b)->Double.compare(b,a));
        Double sum = 0D;
        for(int num : nums){
            sum+=num;
            pq.offer((double) num);
        }
        Double half = sum/2;
        int res = 0;
        while(sum >half){
            Double max = pq.poll()/2;
            sum -= max;
            pq.offer(max);
            res++;
        }
        return res;
    }

    public long maximumSubsequenceCount(String text, String pattern) {
        StringBuilder sb = new StringBuilder();
        int c0 = 0;
        int c1 = 0;
        char char0 = pattern.charAt(0);
        char char1 = pattern.charAt(1);
        for(char c : text.toCharArray()){
            if(c== char0 ||c== char1){
                if(c== char0){
                    c0++;
                }else{
                    c1++;
                }
                sb.append(c);
            }
        }

        return numDistinct(text,pattern) + Math.max(c1,c0);
    }

    public long numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        long[][] dp = new long[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }
        for (int i = m - 1; i >= 0; i--) {
            char sChar = s.charAt(i);
            for (int j = n - 1; j >= 0; j--) {
                char tChar = t.charAt(j);
                if (sChar == tChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        new Question6020().countCollisions("RLRSLL");
    }


    public int countCollisions(String directions) {
        int n = directions.length();
        int res = 0;
        char[] dirs = directions.toCharArray();
        boolean[] deal = new boolean[n];
        boolean handle = false;
        while(handle!=true){

            for(int i = 0; i<n ; i++){
                if(deal[i]){
                    continue;
                }
                if(i<n-1){
                    if(dirs[i]=='R' && dirs[i+1]== 'L'){

                        res+=2;
                        dirs[i] = 'S';
                        dirs[i+1] = 'S';
                        deal[i] = true;
                        deal[i+1] = true;
                    }else if((dirs[i]=='R' && dirs[i+1]=='S') || (dirs[i]=='S' && dirs[i+1]=='L')){
                        res++;
                        dirs[i] = 'S';
                        dirs[i+1] = 'S';
                        deal[i] = true;
                        deal[i+1] = true;
                    }
                }

                if(dirs[i]=='S'){
                    deal[i] = true;
                }else if(i==0){
                    deal[0]= dirs[i]=='L';
                }else if(i == n-1){
                    deal[n-1]= dirs[i]=='R';

                }else {
                    if(deal[i-1]&& dirs[i-1]=='L' && dirs[i]=='L'){
                        deal[i] = true;
                    }
                    if(deal[i+1]&& dirs[i-1]=='R' && dirs[i]=='R'){
                        deal[i] = true;
                    }
                }

            }
            handle = true;
            for(boolean d :deal){
                handle &= d;
            }

        }
        return res;
    }
}
